package top.lcm889.oj.leetcodeTop200;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import static java.lang.System.*;

/**
 * @author Coder-lcm
 * @date 2021/4/6
 *
 *      回溯算法经典例题
 */
public class LC46_全排列 {
    List<List<Integer>> res = new ArrayList<>();

    /**
     * 回溯
     * @param nums 选择列表
     * @param route 路径
     * @return
     */
    public void backtrack(int[] nums, LinkedList<Integer> route) {
        // 回溯的触发结束条件
        if (route.size() == nums.length) {
            res.add(new LinkedList(route));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除已经走过的路径
            if (route.contains(nums[i])) {
                continue;
            }
            // 做选择
            route.add(nums[i]);
            // 进入下一层决策树
            backtrack(nums, route);
            // 递归结束，撤销选择
            route.removeLast();
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        // 已经走过的路径
        LinkedList<Integer> route = new LinkedList<>();
        backtrack(nums, route);
        return res;
    }

    public static void main(String[] args) {
        LC46_全排列 test = new LC46_全排列();
        List<List<Integer>> res = test.permute(new int[]{8,7,6,5,4,3});
        res.forEach(each-> {
            out.print("[");
            each.forEach( e-> {
                out.print(e + ",");
            });
            out.print("]\n");
        });
        out.println("总记录数：" + res.size());
    }

}
